package com.lw.leetcode.other.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 2183. 统计可以被 K 整除的下标对数目
 *
 * @author liw
 * @version 1.0
 * @date 2023/1/31 16:27
 */
public class CountPairs {

    public static void main(String[] args) {
        CountPairs test = new CountPairs();

        // 7
//        int[] arr = {1, 2, 3, 4, 5};
//        int k = 2;

        // 0
//        int[] arr = {1, 2, 3, 4};
//        int k = 5;

        // 27
        int[] arr = {10, 10, 6, 9, 3, 7, 4, 3, 8, 8};
        int k = 4;

        //
//        int[] arr = Utils.getArr(10000, 1, 10000);
//        int k = 2;

        long l = test.countPairs(arr, k);
        System.out.println(l);

    }

    public long countPairs(int[] nums, int k) {
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = (int) Math.pow(k, 0.5); i > 1; i--) {
            if ((k % i) == 0) {
                list.add(i);
                map.put(i, 0);
                if (i * i != k) {
                    list.add(k / i);
                    map.put(k / i, 0);
                }
            }
        }
        int length = nums.length;
        long sum = 0;
        long count = 0;
        for (int num : nums) {
            if ((num % k) == 0) {
                count++;
                continue;
            }
            int gcd = gcd(num, k);
            if (gcd == 1) {
                continue;
            }
            sum += map.get(k / gcd);
            for (Integer v : list) {
                if ((num % v) == 0) {
                    map.merge(v, 1, (a, b) -> a + b);
                }
            }
        }
        sum += ((length - 1 + length - count) * count >> 1);
        return sum;
    }

    private int gcd(int a, int b) {
        if (b == 0) {
            return a;
        }
        return gcd(b, a % b);
    }

}
